#ifndef MYHASH_H
#define MYHASH_H

#include "myvector.h"
#include <iostream>


class KeyNotInHashException : public std::exception {};
class KeyAlreadyInHashException : public std::exception {};


/**
 * this class implements a hash table using double-hashing
 */
template <class TVAL>
class myHash
{
public:
	myHash()
		: _hashtable(_initialSize, Cell()), _size(0)
	{}

	/**
	 * this inserts a key-value to the hash table
	 * \remarks Amortized time of O(1)
	 */
	void InsertKey(int key, const TVAL& val)
	{
		if (FindKey(key, NULL))
		{
			throw KeyAlreadyInHashException();
		}

		int step=0;
		int firshHashKey = HashKey(key, step, _hashtable.Size());
		int currHashKey = firshHashKey;
		while(_hashtable[currHashKey].Status == Cell::Full)
		{
			currHashKey = HashKey(key, ++step, _hashtable.Size());
			if (currHashKey==firshHashKey)
			{
				throw std::exception();
			}
		}
		_hashtable[currHashKey] = Cell(key, val);

		_size += 1;
		UpdateSize();
	}

	/**
	 * this deletes a key-value from the hash table
	 * \remarks Amortized time of O(1)
	 */
	void DeleteKey(int key)
	{
		int step=0;
		int firstHashKey = HashKey(key, step, _hashtable.Size());
		int currHashKey = firstHashKey;
		Cell curr = _hashtable[currHashKey];
		while(curr.Status != Cell::Empty)
		{
			if (curr.Full && curr.Key == key)
			{
				_hashtable[currHashKey].Status = Cell::Deleted;

				_size -= 1;
				UpdateSize();
				return;
			}
			currHashKey = HashKey(key, ++step, _hashtable.Size());
			if (currHashKey==firstHashKey)
			{
				throw std::exception();
			}
			curr = _hashtable[currHashKey];
		}
	}

	/**
	 * this finds a key in the hash table
	 * \return a boolean values which states if the output was valid
	 * \param a key to find
	 * \param where the result is returned
	 * \remarks average time of O(1)
	 */
	bool FindKey(int key, TVAL* res) const
	{
		int step=0;
		int firstHashKey = HashKey(key, step, _hashtable.Size());
		Cell curr = _hashtable[firstHashKey];
		while(curr.Status != Cell::Empty)
		{
			if (curr.Status == Cell::Full && curr.Key == key)
			{
				if (res!=NULL)
				{
					*res = curr.Value;
				}
				return true;
			}
			int newHashKey = HashKey(key, ++step, _hashtable.Size());
			if (newHashKey==firstHashKey)
			{
				return false;
			}
			curr = _hashtable[newHashKey];
		}
		return false;
	}

	/**
	 * this is a wrapper for the previous FindKey
	 * \return the value
	 * \remarks this throws an a exception if a key is not found within the table
	 */
	TVAL FindKey(int key) const
	{
		TVAL res;
		if (FindKey(key, &res))
		{
			return res;
		}
		else
		{
			throw KeyNotInHashException();
		}
	}

	int Size() const
	{
		return _size;
	}

private:
	struct Cell
	{
		Cell()
			: Status(Empty)
		{}

		Cell(int key, TVAL val)
			: Status(Full), Key(key), Value(val)
		{
		}

		enum { Empty, Full, Deleted } Status;
		int Key;
		TVAL Value;
	};

	/**
	 * this function rehashes the table to a new size
	 * \param the new capacity
	 * \remarks complexity of O(Capacity) ~ in practical usage O(n) linear complexity
	 */
	void Rehash(int capacity)
	{
		myVector<Cell> newHash(capacity, Cell());
		for (int i=0; i<_hashtable.Size(); ++i)
		{
			if (_hashtable[i].Status == Cell::Full)
			{
				int step=0;
				int key = _hashtable[i].Key;
				int hKey = HashKey(key, step, capacity);
				while(newHash[hKey].Status == Cell::Full)
				{
					hKey = HashKey(key, ++step, capacity);
				}
				newHash[hKey] = Cell(key, _hashtable[i].Value);
			}
		}

		_hashtable = newHash;
	}

	/**
	 * this functio calculates and returns a hash key for the given parameters
	 * \return a hash key
	 * \remarks complexity O(1)
	 */
	int HashKey(int key, int step, int hashMod) const
	{
		return ((key % hashMod) + step * (1 + (key * _hashConstant))) % hashMod;
	}


	/**
	 * changes the reserved size of the table if necessary
	 * \remarks complexity O(n) if rehash is needed otherwise O(1)
	 */
	void UpdateSize()
	{
		if (_hashtable.Size() == _size )
		{
			Rehash(_size * 2); // make it bigger
		}
		else if (_size * 4 <= _hashtable.Size() && _hashtable.Size()>=_initialSize*4)
		{
			Rehash(_size * 2); // make it smaller
		}
	}


	myVector<Cell> _hashtable;
	int _size;

	static const int _initialSize = 3;
	static const int _hashConstant = 6;
};


#endif // MYHASH_H
